Computer networks are well known, and are used to interconnect computers at different locations so that they can share data and communicate with each other. Originally, most of the data carried on networks comprised textual data. More recently, multimedia data such as animation, voice and video clips have become more popular on the Internet. Multimedia networking products such as Internet telephony, Internet TV and video conferencing have also become popular.
The use of multimedia networking relies on hardware infrastructure, software infrastructure and application tools to support multimedia transport on networks. Multimedia networking is a relatively complex and difficult operation to accomplish. Compared with traditional textual applications, multimedia applications usually require much higher bandwidth. For example, a typical piece of 25-second 320×240 QuickTime movie could take 2.3 MB, which is equivalent to about 1000 screens of textual data.
Further, most multimedia applications require real-time traffic wherein audio and video data are played back continuously at the rate they are sampled. When the data does not arrive in time, the play back process stops and human ears and eyes can easily pick up the artifact. In Internet telephony, human beings can tolerate a latency of about 250 milliseconds. If the latency exceeds this limit users will complain about the quality of the call. In addition to the delay, network congestion also has an effect on real-time traffic. For non-real-time traffic, when the network is congested the transfer takes longer to complete. If no action is taken to remedy the congestion, the retransmission of lost packets aggravates the situation by further congesting the network. However, for real-time data transmission, if the network is congested, the real-time data becomes obsolete and is dropped if it does not arrive in time.
Networks, such as the Internet, are shared by thousands of users, and have limited bandwidth, unpredictable delay and unpredictable availability. These characteristics are in direct contrast to multimedia data which is high bandwidth, real-time and bursty by nature.
There are several known ways to transmit multimedia data, such as by utilizing dedicated links, cables and Asynchronous Transfer Mode (ATM) networks. However, it is desirable to use the Internet Protocol to transmit multimedia data, because it has become a ubiquitous protocol.
Dedicated links and cables are generally more expensive for transmitting multimedia data because they require special installation and special software. Without an existing technology like Local Area Networks (LANs) and/or Wide Area Networks (WANs), software development can be extremely expensive. While ATM may support multimedia data rates because ATM supports high bandwidth, is connection-oriented and can tailor different levels of quality of service to different type of applications, few users have ATM connections at their desktops.
On the other hand, the Internet is growing exponentially. The well-established LAN and WAN technologies based on the IP protocol suite connect bigger and bigger networks all over the world to the Internet. The Internet has become the platform of most networking activities. This is the driving force behind the development and implementation of multimedia protocols over an internet. Another benefit of running multimedia over IP is that users can have integrated data and multimedia service over a single network, without investing in another network and building an interface between networks.
Shared network resources are unpredictable in their availability. Real-time applications require adequate bandwidth when the transmission takes place. Therefore there should be some mechanism for allowing real-time applications to preempt the resources they need along the transmission path, within the limited bandwidth assigned for real-time traffic, and also there should be a mechanism to block real-time applications from using more aggregate bandwidth than was assigned for that class of traffic.
The Internet is a packet-switching network where packets are routed independently across shared networks. There is no guarantee that real-time data will reach the destination without being jumbled and jerky. Appropriate transport protocols should be used to take care of the timing issues so that audio and video data can be played back continuously with correct timing and synchronization.
The Internet carries all types of traffic, and each type of traffic has different characteristics and requirements. For example, a file transfer application requires that some quantity of data be transferred in an acceptable amount of time, while Internet telephony requires that most packets get to the receiver in less than 0.3 seconds. If enough bandwidth is available, best-effort service fulfills all of these requirements. When resources are scarce or overloaded, however, real-time traffic suffers from the congestion.
One solution for multimedia over IP is to classify all traffic, allocate priority for different applications and to make reservations. An Internet Service model named Integrated Services (IntServ) includes best-effort service and real-time service. The real-time service enables IP networks to provide quality of service (QoS) to multimedia applications. A Resource ReServation Protocol (RSVP), together with a Real-time Transport Protocol (RTP), a Real-Time Control Protocol (RTCP), and a Real-Time Streaming Protocol (RTSP), provide a working foundation for real-time services. Integrated Services allows applications to configure and manage a single infrastructure for multimedia applications and traditional applications. It is a comprehensive approach to provide applications with the type of service they need and in the quality they choose. However, IntServ makes heavy demands on the network routers, and has not been widely implemented.
Resource ReSerVation Protocol (RSVP) is a network control protocol that allows a data receiver to request a special end-to-end quality of service for its data flows. Real-time applications use RSVP to reserve necessary resources at routers along the transmission paths so that the requested bandwidth is available when the transmission actually takes place.
Reservations are implemented through two types of RSVP messages: PATH messages and RESV messages. The PATH messages are sent periodically from the sender to the multicast address. A PATH message contains a sender template (data format, source address, source port) and traffic characteristics. This information is used by receivers to find the reverse path to the sender and to determine what resources should be reserved.
RESV messages are generated by the receivers and contain reservation parameters. The reservation parameters define what packets in the flow should be used by the packet classifier. RESV messages follow the exact reverse path of PATH messages, setting up reservations for one or more senders at every node.
The reservation states that RSVP builds at the routers are dynamic in nature. The RSVP daemon sends refresh messages periodically to maintain the reservation states. The absence of a refresh message within a certain time will destroy the reservation state.
The reservation process does not actually transmit the data and provide the requested quality of service. RSVP guarantees the required network resources are available when the transmission actually takes place.
Although RSVP sits on top of IP in the protocol stack, it is not a routing protocol, but rather an Internet control protocol. RSVP relies on the underlying routing protocols to find where it should deliver the reservation requests. When the RSVP-managed flow changes its path, the routing module notifies the RSVP module of the route changes. Therefore, RSVP can quickly adjust the resource reservation to new routes.
There are several reasons for not using IntServ with RSVP for IP telephony. Although IntServ with RSVP would work on a private network with small amounts of traffic, the large number of voice calls that IP Telephony Service Providers carry on their networks would stress an IntServ RSVP system. First, the bandwidth required for RSVP messages would be a significant part of the overall traffic. Second, RSVP router code was not designed to support many thousands of simultaneous connections per router.
It should be noted, however, that RSVP is a signaling protocol, and it has been proposed for use in contexts other than IntServ. For example, RSVP-TE is a constraint-based routing protocol for establishing Label Switched Paths with associated bandwidth and specified paths in an MPLS network. RSVP has also been proposed as the call admission control mechanism for VoIP in differentiated services networks.
Since IntServ with RSVP does not scale well to support many thousands of connections, the IETF has developed a simpler framework and architecture to support differentiated services (DiffServ). The architecture achieves scalability by aggregating traffic into classifications that are conveyed by means of IP-layer packet marking using the DS field in Ipv4 or Ipv6 headers. Sophisticated classification, marking, policing, and shaping operations need only be implemented at network boundaries. Service provisioning policies allocate network resources to traffic streams by marking and conditioning packets as they enter a differentiated services-capable network, in which the packets receive a particular per-hop forwarding behavior (PHB) based on the value of the DS field.
The primary goal of differentiated services is to allow different levels of service to be provided for traffic streams on a common network infrastructure. A variety of resource management techniques may be used to achieve this, but the end result will be that some packets will receive different (e.g. better) service than others. Service providers can, for example, offer a real-time service giving priority in use of bandwidth and router queues, up to the configured amount of capacity allocated to real-time traffic.
One candidate PHB for voice service is Expedited Forwarding (EF). The objective of the EF PHB is to build a low loss, low latency, low jitter, assured bandwidth, end-to-end service through DS domains. Such a service would appear to endpoints like a point-to-point connection of “virtual leased line”. Since router queues cause traffic to experience loss, jitter, and excessive latency, EF PHB tries to ensure that all EF traffic experiences either no or very small queues.
For several decades, traffic engineering and automated rerouting of telephone traffic have increased the efficiency and reliability of the PSTN. Frame relay and ATM also offer source (or “explicit”) routing capabilities that enable traffic engineering. However, IP networks have relied on destination-based routing protocols that send all the packets over the shortest path, without regard to the utilization of the links comprising that path. In some cases, links can be congested by traffic that could be carried on other paths comprised of underutilized links. It is possible to design an IP network to run on top of a frame relay or ATM (“Layer 2”) network, providing some traffic engineering features, but this approach adds cost and operational complexity.
MutliProtocol Label Switching (MPLS) offers IP networks the capability to provide traffic engineering as well as a differentiated services approach to voice and multimedia quality. MPLS separates routing from forwarding, using label swapping as the forwarding mechanism. The physical manifestation of MPLS is the Label Switch Router (LSR). LSRs perform the routing function in advance by creaing Label Switched Paths (LSPs) connecting edge routers. The edge router (an LSR) attaches short (four-byte) labels to packets. Each LSR along the LSP swaps the label and passes it along to the next LSR. The last LSR on the LSP removes the label and treats the packet as a normal IP packet.
MPLS LSPs can be established using Label Distribution Protocol (LDP), RSVP Traffic Engineering (RSVP-TE), or Constraint-Based LDP (CR-LDP). When using LDP, LSPs have no associated bandwidth. However, when using RSVP-TE or CR-LDP, each LSP can be assigned a bandwidth, and the path can be designated for traffic engineering purposes. MPLS traffic engineering (MPLS-TE) combines extensions to OSPF or IS-IS, to distribute link resource constraints, with the label distribution protocols RSVP-TE or CR-LDP. Resource and policy attributes are configured on every link and define the capabilities of the network in terms of bandwidth, a Resource Class Affinity string, and a traffic engineering link metric. When performing the constraint-based path computation, the originating LSR compares the link attributes received via OSPF or IS-IS to those configured on the LSP.
Differentiated Services can be combined with MPLS to map DiffServ Behavior Aggregates onto LSPs. QoS policies can be designated for particular paths. More specifically, the EXP field of the MPLS label can be set so that each label switch/router in the path knows to give the voice packets highest priority, up to the configured maximum bandwidth for voice on a particular link. When the high priority bandwidth is not needed for voice, it can be used for lower priority classes of traffic.
DiffServ and MPLS DiffServ are implemented independently of the routing computation. MPLS-TE computes routes for aggregates across all classes, and performs admission control over the entire LSP bandwidth. MPLS-TE and MPLS DiffServ can be used at the same time. Alternatively, DiffServ can be combined with traffic engineering to establish separate tunnels for different classes. DS-TE makes MPLS-TE aware of DiffServ, so that one can establish separate LSPs for different classes, taking into account the bandwidth available to each class. So, for example, a separate LSP could be established for voice, and that LSP could be given higher priority than other LSPs, but the amount of voice traffic on a link could be limited to a certain percentage of the total link bandwidth.
RSVP version 1 lacks facilities for aggregation of individual reserved sessions into a common class. IETF RFC 3175 (Aggregation of RSVP for IPv4 and IPv6 Reservations) specifies several options for aggregated reservations: One method is to use Differentiated Services mechanisms for classification and scheduling of traffic supported by aggregate reservations. “It is not only independent of the number of E2E reservations, it is also independent of the number of aggregate reservations in the aggregation region. One or more Diff-Serv DSCPs are used to identify traffic covered by aggregate reservations and one of more Diff-Serv PHBs are used to offer the required forwarding treatment to this traffic.”
Sites sharing a common IP network may be divided into several subsets. A Virtual Private Net (VPN) may be defined to be a subset of sites. Two sites can only have IP connectivity if they both belong to one of these VPNs. (Note that a site may belong to more than one VPN.)
VPNs are well known in the art. One type of VPN is a Multiprotocol Label Switching (MPLS) based VPN. (Ref: IETF RFC 2547 and RFC 2547bis) An MPLS-based VPN typically includes multiple sites transmitting and receiving data across a Service Provider Backbone (SPB). Internal to the SPB are Provider Edge (PE) routers, which transmit and receive data into and out of the SPB. Routing of data from one PE to another PE within the SPB may include the use of Provider (P) routers. The P routers transmit and receive data from a PE router or another P router.
At each customer site there are devices that are used to communicate over the SPB. Those customer devices that are attached to PE routers are called Customer Edge (CE) devices. A CE device may be a computer, but typically it is a router, in which case we refer to it as a CE router. The PE router is attached to a CE device by being the endpoint of an interface or “sub-interface” (e.g., PVC, VLAN, etc.) whose other endpoint is a CE device.
Each PE router maintains several separate forwarding tables, known as VPN Routing and Forwarding tables, or VRF tables. When a PE router receives a data packet from a CE device, it looks in the VRF table associated with that CE device to determine how to route the packet. The VRF table associated with a particular CE interface contains only routes that lead to other CE interfaces (i.e., other sites) that have at least one VPN in common with the sending CE device.
CE routers transmit and receive data into and out of the customer network. These CE routers use VPNs to exchange information between customer devices at different sites. Typically, only the PE routers are aware of the VPNs. MPLS VPNs do not have defined end-to-end (CE-CE) connections, and therefore are substantially more scalable and easier to build and manage, than conventional VPNs.
MPLS VPNs offer a platform for rapid deployment of additional value-added IP services, including intranets, extranets, voice, multimedia, and network commerce. Privacy and security are provided by limiting the distribution of a VPN's routes to only those routers that are members of the VPN.
PE routers establish Label Switched Paths (LSPs) to the other PE routers. For each VPN, the VRF table in the PE router contains a label designating either a pointer to an outgoing interface on the destination PE router, or a VPN identifier to be used when the destination PE needs to look at its VRF to forward an incoming packet. The PE router places this VPN label on the packet. Then, if path to the destination PE is through a P router, the originating PE router places an LSP label on the packet, so that the VPN label becomes the inner label. Thus P routers never observe the VPN label. Typically, the penultimate Label Switch Router pops the outer label before sending the packet to the destination PE, so that the destination PE observes only the VPN label, from which it determines the outgoing interface. Then it pops the VPN label, sending the original packets to the correct destination CE router. This technology is well known in the industry.
Several VPNs may share an LSP between two PE routers. It is, therefore, possible for one VPN to transmit more than its share of traffic on an LSP, exceeding its committed rate, to the detriment of other VPNs. More specifically, the intermediate P routers do not observe the inner labels identifying a labeled packet as belonging to one or another VPN. Therefore, there is no simple way for the core of the network to determine how much capacity is being used by any of the VPNs.
In view of the foregoing it would be desirable to provide a method of allocating capacity to MPLS VPNs fairly, so that one VPN is not starved by the greediness of another VPN sharing the same LSP.